package leetcode.array;

/**
 * @description:
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * @author: cyy
 **/
public class Demo20211123_1 {
    public static void main(String[] args) {
        int[] a = {1,3};
        int[] ints = searchRange(a,1);
        System.out.println("result:" + ints[0] + "========"  + ints[1]);
    }

    public static  int[] searchRange(int[] nums, int target) {
        int[] res = {-1,-1};
        if(nums.length == 0){
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        if(nums.length == 1){
            if(nums[0] == target){
                res[0] = 0;
                res[1] = 0;
            }else{
                res[0] = -1;
                res[1] = -1;
            }
            return res;
        }
        int left = 0;
        int right = nums.length ;
        while(left <= right && res[0] == -1 && res[0] == -1){
            int mid = (left + right) /2 ;
            //中间像两边外侧巡检判断
            if(target == nums[mid]){
                //判断左边target，最大为nums[mid]
                int right2 = mid;
                while (left < right2){
                    int mid1 = (left + right2) / 2;
                    if (nums[mid1] == nums[mid]){
                        right2 = mid1 ;
                    }
                    if (nums[mid1] < nums[mid]){
                        left = mid1 + 1;
                    }
                }
                res[0] = right2;
                int left2 = mid;
                //判断右边target,最小为nums[mid]
                int i = right == nums.length ? right - 1 : right;
                while (i >= left2){
                    int mid2 = (left2 + i) / 2 ;
                    if (nums[mid2] == nums[mid]){
                        left2 = mid2 + 1;
                    }
                    if (nums[mid2] > nums[mid]){
                        i = mid2 - 1;
                    }
                }
                res[1] = left2 - 1;
            }else if(target < nums[mid]){
                right = mid - 1 ;
            }else if (target  > nums[mid]){
                left  =  mid + 1 ;
                if (left == nums.length){
                    //索引越界
                    left ++ ;
                }
            }
        }
        return res;
    }

    public static  int[] searchRange2(int[] nums, int target) {
        int[] res = {-1,-1};
        if(nums.length == 0){
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        if(nums.length == 1){
            if(nums[0] == target){
                res[0] = 0;
                res[1] = 0;
            }else{
                res[0] = -1;
                res[1] = -1;
            }
            return res;
        }
        int left = 0;
        int right = nums.length;
        //查找左边界
        while(left < right){
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid; // 注意
            }
        }
        res[0] = left;
        //查找右边界
        int left1 = 0, right1 = nums.length;
        while (left1 < right1) {
            int mid = (left1 + right1) / 2;
            if (nums[mid] == target) {
                left1 = mid + 1; // 注意
            } else if (nums[mid] < target) {
                left1 = mid + 1;
            } else if (nums[mid] > target) {
                right1 = mid;
            }
        }
        res[1] = left1 - 1;
        return  res;
    }
}
